//----------------------------------------------------------------------因子分解

//pollard_rho 找出一个非平凡因子
//             依赖:数论基础-> gcd() & mod_mult()
LL pollard_rho(LL n,int c)
{
	LL x,y,d,i=1,k=2;
	x=rand()%(n-1)+1;
	y=x;
	while(1)
	{
		i++;
		x=(mod_mult(x,x,n)+c)%n;
		d=gcd(y-x,n);
		if(d>1&&d<n)return d;
		if(x==y)return n;
		if(i==k)y=x,k<<=1;
		if(k>(1<<11))return n;//卡时用
	}
}
